Pumping Lemma

The pumping lemma is a tool for proving a language is not regular. It cannot prove a language is regular -- only that it isn't.

It states that for any regular language L, there exists a pumping length p\in\mathbb{N}_+ such that any string w\in L, |w| \geq p can be divided into three substrings xyz, satisfying the following conditions:

\begin{align} |xy| &\leq p \\ |y| &\geq 1 \\\\ \forall i \in \mathbb{N}_0 : &xy^iz\in L \end{align}

The Idea

Every regular language has a fintie automaton recognising it. If that automaton has p states and you feed it a string of length \geq p, the machine must revisit some state -- creating a loop. That loop can be repeated (pumped) any number of times and the resulting string must still be in the language.

Using It to Prove Non-Regularity

The proof structure is always a game against an adversary:

Assume L is regular, so a pumping length p exists.
You pick a string s \in L with |s| \geq p (choose cleverly).
The adversary splits s = xyz subject to the constraints above.
You show that for some i, xy^iz \notin L.
Conclude L is not regular.

Classic Example

Claim: L = \{a^n b^n \mid n \geq 0\} is not regular.

Proof:

Assume L is regular with pumping length p.
Choose s = a^p b^p \in L, so |s| = 2p \geq p.
Any split xyz with |xy| \leq p and |y| \geq 1 means y = a^k for some k \geq 1 (it lies entirely in the a-block).
Pump with i = 2: xy^2z = a^{p+k}b^p.
Since k \geq 1, the counts of as and bs differ, so xy^2z \notin L.

Therefore L is not regular. \blacksquare